package day07;

import java.util.HashSet;


/**
 * No3003.
 * https://leetcode.cn/problems/maximize-the-number-of-partitions-after-operations/
 */
public class No3003 {

    /**
     * 官方题解
     */
    public int mPAOOffical(String s, int k){
        int n = s.length();
        int[][] left = new int[n][3];
        int[][] right = new int[n][3];

        int num = 0, mask = 0, count = 0;
        for (int i = 0; i < n - 1; i++) {
            int binary = 1 << (s.charAt(i) - 'a');
            if ((mask & binary) == 0) {
                count++;
                if (count <= k) {
                    mask |= binary;
                } else {
                    num++;
                    mask = binary;
                    count = 1;
                }
            }
            left[i + 1][0] = num;
            left[i + 1][1] = mask;
            left[i + 1][2] = count;
        }

        num = 0;
        mask = 0;
        count = 0;
        for (int i = n - 1; i > 0; i--) {
            int binary = 1 << (s.charAt(i) - 'a');
            if ((mask & binary) == 0) {
                count++;
                if (count <= k) {
                    mask |= binary;
                } else {
                    num++;
                    mask = binary;
                    count = 1;
                }
            }
            right[i - 1][0] = num;
            right[i - 1][1] = mask;
            right[i - 1][2] = count;
        }

        int maxVal = 0;
        for (int i = 0; i < n; i++) {
            int seg = left[i][0] + right[i][0] + 2;
            int totMask = left[i][1] | right[i][1];
            int totCount = Integer.bitCount(totMask);
            if (left[i][2] == k && right[i][2] == k && totCount < 26) {
                seg++;
            } else if (Math.min(totCount + 1, 26) <= k) {
                seg--;
            }
            maxVal = Math.max(maxVal, seg);
        }
        return maxVal;
    }

    public int maxPartitionsAfterOperations(String s, int k) {

        if(k >= 26) return 1;

        int splitCount = 0; // answer
        boolean skill = true; // check whether the skill is still availabe or not;
        boolean charRepeat = false;
        HashSet<Character> chs = new HashSet<Character>(); // chs : char hashset

        int len = s.length();
        char[] ca = s.toCharArray(); // cs : char array
        for(int i=0; i<len; i++){
            if(chs.contains(ca[i])) charRepeat = true;
            else chs.add(ca[i]);

            if(chs.size() < k-1) continue;
            else if(chs.size() == k-1){
                while(i+1<len && chs.contains(ca[i+1])){
                    i++;
                    charRepeat = true;
                }
                if(charRepeat && skill){
                    chs.clear();
                    splitCount++;
                    skill = false;
                }else continue;
            }else{
                if(!skill){
                    while(i+1<len && chs.contains(ca[i+1])) i++;
                }
                chs.clear();
                splitCount++;
                charRepeat = false;
            }
        }
        if(chs.size()>0) splitCount++;
        return splitCount;
    }
}
